package demo.java.util;

import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
import java.util.Random;

import org.junit.Assert;
import org.junit.BeforeClass;
import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

/**
 * JAVA中BitSet就是“位图”数据结构，根据“位图”的语义，数据的存在性可以使用bit位上的1或0来表示；一个bit具有2个值：0和1，正好可以用来表示false和true。
 * 对于判断“数据是否存在”的场景，我们通常使用HashMap来存储，不过hashmap这个数据结构KEY和Value的保存需要消耗较多的内存，不适合保存较多的数据，即大数据场景；
 * 
 * <p>
 * 所谓“存在性”，就是通过BitSet来检测一个数字是否存在。
 * <p>
 * JAVA中，一个long型数字占用64位空间，根据上述“位图”的概念，那么一个long型数字（4个字节）就可以保存64个数字的“存在性”状态(无碰撞冲突时，即true、false状态)。
 * 比如50个数字{0,1,10,...63}，判定“15”是否存在，那么我们通常会首先将这些数字使用数组或者hashmap保存，然后再去判定，那么保存这些这些数据需要占用64 * 64位；
 * 如果使用位图，那么一个long型数字即可。（如果换成50个字符串，那么其节约的空间可能更大）。
 * <p>
 * <li>1) BitSet只面向数字比较，比如set(int a,boolean value)方法，将数字a在bitSet中设定为true或者false；此后可以通过get(int a)方法检测结果。
 * 对于string类型的数据，如果像使用BitSet，那么可以将其hashcode值映射在bitset中。
 * 
 */
public class BitSetDemo {

    private static Logger logger = LoggerFactory.getLogger(BitSetDemo.class);

    /**
     * <li>首先我们需要知道：1，1<<64，1<<128，1<<192...等，这些数字的计算结果是相等的（位运算）；这也是一个long数字，只能表达连续的(或者无冲突的)64个数字的状态，
     * 即如果把数字1在long中用位表示，那么数字64将无法通过同一个long数字中位表示--冲突；BitSet内部，是一个long[]数组，数组的大小由bitSet接收的最大数字决定，
     * 这个数组将数字分段表示[0,63],[64,127],[128,191]...。即long[0]用来存储[0,63]这个范围的数字的“存在性”，long[1]用来存储[64,127]，依次轮推，这样就避免了位运算导致的冲突。
     * <li>bitSet内部的long[]数组是基于向量的，即随着set的最大数字而动态扩展。数组的最大长度计算：(maxValue - 1) >> 6 + 1
     * <li>BitSet可以有效的降低内存的使用量，但是它的内存使用量是有内部long数组的大小决定，所以在创建BitSet时指定的值域非常重要，过大的值域将会导致OOM（比如指定Long.MAX_VALUE）,
     * 在一个BitMap上存储Integer.MAX_VALUE个“着色”（注意，BitSet只能对正数操作），大概消耗128M内存。
     */
    @Test
    public void bit() {
        logger.info("1<<64 = {}", 1 << 64);
        logger.info("1<<128 = {}", 1 << 128);
        logger.info("1<<192 = {}", 1 << 192);
        long value = 64L;
        logger.info("2的6次方={}", Math.pow(2, 6));
        logger.info("以2为底的64的对数={}", Math.log(64) / Math.log(2));
        logger.info("value的bit数组：{}", Long.toBinaryString(value));
        logger.info("value -1 的bit数组：{}", Long.toBinaryString(value - 1));
        logger.info("(value - 1) >> 6)的bit数组：{}", Long.toBinaryString((value - 1) >> 6));
        logger.info("数字右移6位等同于除以64.如128>>6={},128/64={}", 128 >> 6, 128 / 64);

    }

    /**
     * 比如在有10亿条URL中判定一个“www.baidu.com/a”是否存在，如果我们使用常规的hashmap来保存将是不现实的，因为URL本身需要占据较多的内存而无法直接操作。
     * 如果我们使用bitset来保存，那么可以对一条URL求hashcode，并将数字映射在bitset上，那么事实上它只需要bitset上的一个bit位即可， 即我们1位空间即可表达一个URL字符串的存在性。
     * <p>
     * 因为BitSet API只能接收int型的数字，即只能判定int数字是否在bitSet中存在。所以，对于String类型，我们通常使用它的hashcode，但这有一种隐患，java中hashcode存在冲突问题，
     * 即不同的String可能得到的hashcode是一样的（即使不重写hashcode方法），如果我们不能很好的解决这个问题，
     * 那么就会出现“数据抖动”---不同的hashcode算法、运行环境、bitSet容量，会导致判断的结果有所不同。这个问题该如何解决或者缓解呢？
     * <li>1）调整hashcode生成算法：我们可以对一个String使用多个hashcode算法，生成多个hashcode，然后在同一个BitSet进行多次“着色”，在判断存在性时，只有所有的着色位为true时，才判定成功。
     * <li>2) 多个BitSet并行保存：改良1)中的实现方式，我们仍然使用多个hashcode生成算法，但是每个算法生成的值在不同的BitSet中着色，这样可以保持每个BitSet的稀疏度(降低冲突的几率)。
     * 在实际结果上，比1)的误判率更低，但是它需要额外的占用更多的内存，毕竟每个BitSet都需要占用内存。这种方式，通常是缩小hashcode的值域，避免内存过度消耗。
     * <li>3) 是否有必要完全避免误判？如果做到100%的正确判断率，在原理上说BitSet是无法做的，
     * BitSet能够保证“如果判定结果为false，那么数据一定是不存在；但是如果结果为true，可能数据存在，也可能不存在(冲突覆盖)”
     */
    @Test
    public void string() {
        logger.info("0x7FFFFFFF = {},bit数组为：{},Integer.Max={}", 0x7FFFFFFF, Long.toBinaryString(0x7FFFFFFF),
                Integer.MAX_VALUE);
        // hashcode的值域,127M
        BitSet bitSet = new BitSet(Integer.MAX_VALUE);

        // 0x7FFFFFFF
        String url = "http://baidu.com/a";
        int hashcode = url.hashCode() & 0x7FFFFFFF;
        bitSet.set(hashcode);

        logger.info("着色位的个数:{}", bitSet.cardinality());
        logger.info("检测存在性:{}", bitSet.get(hashcode));
        // 清除位数据
        bitSet.clear(hashcode);
        logger.info("清除位数据后检测存在性:{}", bitSet.get(hashcode));

    }

    /**
     * (布隆姆过滤器) BloomFilter 的设计思想和BitSet有较大的相似性，目的也一致，它的核心思想也是使用多个Hash算法在一个“位图”结构上着色，最终提高“存在性”判断的效率。
     */
    @Test
    public void bloomFilter() {
        // 指定bloomFilter的容量
        BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(StandardCharsets.UTF_8),
                2 << 21);
        String url = "www.baidu.com/a";
        bloomFilter.put(url);
        System.out.println(bloomFilter.mightContain(url));
    }

    @Test
    public void bitSetDemo2() {
        BitSet bits1 = new BitSet(16);
        BitSet bits2 = new BitSet(16);

        // set some bits
        for (int i = 0; i < 16; i++) {
            if ((i % 2) == 0) {
                bits1.set(i);
            }
            if ((i % 5) != 0) {
                bits2.set(i);
            }
        }
        System.out.println("Initial pattern in bits1: ");
        System.out.println(bits1);
        System.out.println("\nInitial pattern in bits2: ");
        System.out.println(bits2);

        // AND bits
        bits2.and(bits1);
        System.out.println("\nbits2 AND bits1: ");
        System.out.println(bits2);

        // OR bits
        bits2.or(bits1);
        System.out.println("\nbits2 OR bits1: ");
        System.out.println(bits2);

        // XOR bits
        bits2.xor(bits1);
        System.out.println("\nbits2 XOR bits1: ");
        System.out.println(bits2);
    }

    @Test
    public void bitSet() {
        BitSet bitSet = new BitSet();
        bitSet.set(1024);
        logger.info("{}", bitSet);
    }

    // 全量bitset
    private static BitSet allBitSet = new BitSet();
    // 偶数bitset
    private static BitSet evenBitSet = new BitSet();
    // 奇数bitset
    private static BitSet oddBitSet = new BitSet();
    // 空bitset
    private static BitSet emptyBitSet = new BitSet();

    @BeforeClass
    public static void init() {
        for (int i = 0; i < 63; i++) {
            allBitSet.set(i);
            if (i % 2 == 0) {
                evenBitSet.set(i);
            } else {
                oddBitSet.set(i);
            }
        }
    }

    // 测试初始化
    @Test
    public void testInit() {
        // 断点进去看
        BitSet initBitSet1 = new BitSet(55);
        System.out.println(initBitSet1);
        BitSet initBitSet2 = new BitSet(129);
        System.out.println(initBitSet2);
    }

    // 测试基础的and\or\xor运算
    @org.junit.Test
    public void testOper() {
        // System.out.println(evenBitSet.toByteArray());
        evenBitSet.and(allBitSet);
        System.out.println("偶数Bit and 全量Bit：" + evenBitSet);
        evenBitSet.xor(allBitSet);
        System.out.println("偶数Bit xor 全量Bit：" + evenBitSet);
        evenBitSet.or(allBitSet);
        System.out.println("偶数Bit or 全量Bit：" + evenBitSet);
    }

    // 测试动态扩展，每次是以64位为单位
    @org.junit.Test
    public void testExpand() {
        testSize();
        allBitSet.set(100000000);
        System.out.println("全量Bit-设置64之后大小：" + allBitSet.size() / 8 / 1024 / 1024 + "m");
        System.out.println("全量Bit-设置64之后长度：" + allBitSet.length());
        System.out.println("全量Bit-设置64之后实际true的个数：" + allBitSet.cardinality());
    }

    // oddBitSet过滤掉evenBitSet
    @Test
    public void testOddFilterEvenBitSet() {
        oddBitSet.set(2);
        oddBitSet.set(4);
        oddBitSet.set(6);
        System.out.println("过滤前：oddBitSet:" + oddBitSet);
        evenBitSet.and(oddBitSet);
        oddBitSet.xor(evenBitSet);
        System.out.println("oddBitSet过滤evenBitSet相同的元素的结果：" + oddBitSet);
    }

    // 偶数和奇数bitset合并去重之后和allbitSet内容一致
    @Test
    public void testOddAndEventBitSet() {
        oddBitSet.set(2);
        oddBitSet.set(4);
        oddBitSet.set(6);
        System.out.println("偶数BitSet合并前 ：" + evenBitSet);
        System.out.println("奇数BitSet合并前 ：" + oddBitSet);
        System.out.println("------------------------");
        oddBitSet.or(evenBitSet);
        System.out.println("偶数BitSet合并后 ：" + evenBitSet);
        System.out.println("奇数BitSet合并后 ：" + oddBitSet);
        System.out.println("全亮BitSet内容是 ：" + allBitSet);
        Assert.assertTrue(oddBitSet.equals(allBitSet));
    }

    // 返回true的个数
    @org.junit.Test
    public void testCardinality() {
        System.out.println("偶数Bit-true的个数：" + evenBitSet.cardinality());
    }

    // 判断是否为空
    @org.junit.Test
    public void testIsEmpty() {
        System.out.println("全量Bit-判断非空：" + allBitSet.isEmpty());
        System.out.println("空  Bit-判断非空：" + emptyBitSet.isEmpty());
    }

    // 根据下表开始结束获取
    @org.junit.Test
    public void testGetFromEnd() {
        System.out.println("全量Bit-[0,5]：" + allBitSet.get(0, 5));
        System.out.println("空  Bit-[0,5]：" + emptyBitSet.get(0, 5));
    }

    // 判断是否存在bitset
    @org.junit.Test
    public void testGet() {
        System.out.println("全量Bit-下标为2是否存在:" + allBitSet.get(2));
        System.out.println("偶数Bit-下标为1是否存在:" + evenBitSet.get(1));
        System.out.println("偶数Bit-下标为2是否存在:" + evenBitSet.get(2));
    }

    // 计算bitset内存大小
    @org.junit.Test
    public void testSize() {
        System.out.println("空  Bit-大小：:" + emptyBitSet.size() + "byte");
        System.out.println("偶数Bit-大小：" + evenBitSet.size() + "byte");
        System.out.println("全量Bit-大小：" + allBitSet.size() + "byte");
    }

    // 计算bitset长度（bitset最大数+1）
    @org.junit.Test
    public void testLength() {
        System.out.println("全量Bit-长度：" + allBitSet.length());
        System.out.println("偶数Bit-长度：" + evenBitSet.length());
    }

    /**
     * 有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来？
     */
    @Test
    public void bitSetDemo() {
        Random random = new Random();

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 1000_0000; i++) {
            int randomResult = random.nextInt(1_0000_0000);
            list.add(randomResult);
        }
        System.out.println("产生的随机数有");
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
        BitSet bitSet = new BitSet(1_0000_0000);
        for (int i = 0; i < 1000_0000; i++) {
            bitSet.set(list.get(i));
        }

        System.out.println("0~1亿不在上述随机数中有" + bitSet.size());
        for (int i = 0; i < 100000000; i++) {
            if (!bitSet.get(i)) {
                System.out.println(i);
            }
        }
    }
}
